Skip to content
分割数组得到最小绝对差
概述
给定正整数数组 nums，将其分成两个连续非空子数组 left 与 right，并且满足：
left严格递增right严格递减
在所有合法分割中，求左右子数组元素和的差的绝对值的最小值。如果不存在任何合法分割，返回 -1。
基本概念
- 分割点：右子数组的起始下标，记作
k（1 <= k <= n-1）。此时left = nums[0..k-1]，right = nums[k..n-1]。 - 合法分割：同时满足左递增、右递减且两个子数组均非空的分割。
- 目标：最小化
|sum(left) - sum(right)|。
工作原理
先标记出数组中哪些前缀严格递增、哪些后缀严格递减，再枚举所有可能的分割点。
- 计算前缀和数组
prefix，prefix[i]表示前i个元素的和（prefix[0] = 0）。 - 构造
leftInc：leftInc[i]表示子数组nums[0..i]是否严格递增。leftInc[0]永远为true；对i >= 1，leftInc[i] = leftInc[i-1] && nums[i] > nums[i-1]。 - 构造
rightDec：rightDec[i]表示子数组nums[i..n-1]是否严格递减。
从后向前遍历，rightDec[n-1] = true；对i从n-2向下到0，rightDec[i] = rightDec[i+1] && nums[i] > nums[i+1]。 - 枚举分割点
k从1到n-1：- 若
leftInc[k-1]和rightDec[k]同时为true，则分割合法。 - 左和
leftSum = prefix[k]，右和rightSum = prefix[n] - prefix[k]，用|leftSum - rightSum|更新最小值。
- 若
- 遍历结束后若一次合法分割都没遇到，返回
-1；否则返回记录的最小值。
这一过程只扫描数组常数次，时间复杂度为 O(n)。
基本用法
函数签名：
typescript
function splitArray(nums: number[]): numbernums：长度至少为 2 的正整数数组。- 返回值：最小绝对差，若不存在合法分割则返回
-1。
示例
示例 1：多个合法分割
typescript
const nums = [1, 2, 3, 9, 2, 1];
console.log(splitArray(nums)); // 6执行过程：
- 前缀和：
prefix = [0, 1, 3, 6, 15, 17, 18]。 leftInc：[true, true, true, true, false, false]。rightDec从后向前构造：rightDec[5] = true；rightDec[4] = true（2 > 1且rightDec[5]成立）；rightDec[3] = true（9 > 2且rightDec[4]成立）；rightDec[2] = false（3 > 9不成立）；rightDec[1] = false；rightDec[0] = false。- 枚举分割点：
k = 3：leftInc[2]为true，rightDec[3]为true，左和6，右和12，差6。k = 4：leftInc[3]为true，rightDec[4]为true，左和15，右和3，差12。- 其他
k不合法。
- 最小差为
6。
示例 2：整个数组严格递增
typescript
const nums = [1, 2, 3, 4];
console.log(splitArray(nums)); // 2leftInc全为true。rightDec：因为4之后是结束，rightDec[3]为true；3 > 4不成立，所以rightDec[0..2]均为false。- 唯一合法分割点在
k = 3（右子数组[4]），左和6，右和4，差2。
示例 3：无法合法分割
typescript
const nums = [5, 3, 4, 2];
console.log(splitArray(nums)); // -1leftInc：[true, false, false, false]（因为3 < 5立即打破递增）。rightDec：rightDec[3] = true；rightDec[2] = true（4 > 2且rightDec[3]）；rightDec[1] = false（3 > 4不成立）；rightDec[0] = false。- 没有任何
k同时满足leftInc[k-1]为true且rightDec[k]为true，返回-1。
Java 调用示例
java
int result = SplitArray.splitArray(new int[]{1, 2, 3, 4});
System.out.println(result); // 2Python 调用示例
python
print(split_array([1, 2, 3, 9, 2, 1])) # 6注意点
- 右子数组只有一个元素时，按定义视为严格递减（
rightDec[n-1]初始为true），因此像[1,2,3,4]这类全递增数组仍存在合法分割。 - 构建
rightDec时必须从后向前递推，每个位置依赖后方信息。 - 前缀和数组长度设为
n+1可避免下标偏移错误：prefix[0] = 0，prefix[i]表示前i个元素的和。 - 当
nums.length < 2时，无法形成两个非空子数组，直接返回-1。
限制
- 时间复杂度 O(n)，数组仅被扫描常数次。
- 空间复杂度 O(n)，需要存储前缀和以及两个布尔标记数组。若希望 O(1) 附加空间，可将单调性判断与枚举合并，但会牺牲代码清晰性。